1. Technical Field
This application relates to computer systems, and more particularly to scheduling tasks for execution in computer systems.
2. Description of Related Art
Computer systems may include an operating system providing for multi-tasking. Multi-tasking allows users to run multiple programs and gives the appearance that the computer system is executing all of the programs at the same time. The operating system performs multi-tasking by swapping tasks, processes, threads, and the like in and out of an execution or run state.
The operating system may schedule different tasks for execution in accordance with a variety of different criteria. For example, an operating system may schedule a new task for execution if a currently executing task is awaiting completion of a slow I/O operation. A new task may also be scheduled for execution interrupting a current task if the new task has a higher scheduling priority, or if the current task has run a completed time quantum or preset amount.
Drawbacks may exist with the amount of scheduling latency in connection with selecting and scheduling tasks for execution. For example, in connection with a priority-based scheme, the task with the highest priority of all tasks may be selected for execution. As the number of tasks in a “waiting for execution” state increases, the management and selection of the highest priority task may increase. Additionally, an embodiment may further implement an additional policy, such as an age policy, and also schedule a task for execution in connection with how long a task has been in the system, or waiting to execute. Taking into account the various criteria may increase the amount of time in scheduling latency especially as the number of tasks increases in a multi-tasking environment.
It is desirable to provide an efficient task scheduling technique that minimizes scheduling latency while being linearly scalable for use with any number of tasks. Such a technique is described, for example, in U.S. Pat. No. 7,178,146 (the '146 patent), which is assigned to the owner of the present application and incorporated by reference herein. In the '146 patent, each task to be executed is allotted a pie count representing the number of times out of the total run list each task is considered for scheduling. The total run list is the sum of all the pie counts for all tasks. Each time a task starts, exits, or has its pie count reset, the total number of pie counts is computed and tasks are distributed throughout the run list. Each task is distributed in the run list in accordance with its number of pie counts such that a minimum number of intervening tasks appears between each successive appearance of the same task. The scheduler then schedules tasks based on the run list.
The technique disclosed in the '146 patent reruns tasks in the run list without regard to the reason why the task relinquished control in the first place. Furthermore, using a single run list means that every task in the run list would be scheduled without regard to changing conditions or needs of the system. Accordingly, it is desirable to provide a system that addresses these issues.